Sequence reconstruction [Topological Sort]

Time: O(NxS); Space: O(N); medium

Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 104. Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.

Example 1:

Input: org = [1,2,3], seqs = [[1,2],[1,3]]

Output: False

Explanation:

• [1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.

Example 2:

Input: org = [1,2,3], seqs = [[1,2]]

Output: False

Explanation:

• The reconstructed sequence can only be [1,2].

Example 3:

Input: org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]

Output: True

Explanation:

• The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].

Example 4:

Input: org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]

Output: True

class Solution1(object):
    '''
    Time:  O(NxS), N is the size of org, S is the size of seqs.
    Space: O(N)
    '''
    def sequenceReconstruction(self, org, seqs):
        """
        :type org: List[int]
        :type seqs: List[List[int]]
        :rtype: bool
        """
        if not seqs:
            return False
        pos = [0] * (len(org) + 1)
        for i in range(len(org)):
            pos[org[i]] = i

        is_matched = [False] * (len(org) + 1)
        cnt_to_match = len(org) - 1
        for seq in seqs:
            for i in range(len(seq)):
                if not 0 < seq[i] <= len(org):
                    return False
                if i == 0:
                    continue
                if pos[seq[i-1]] >= pos[seq[i]]:
                    return False
                if is_matched[seq[i-1]] == False and pos[seq[i-1]] + 1 == pos[seq[i]]:
                    is_matched[seq[i-1]] = True
                    cnt_to_match -= 1

        return cnt_to_match == 0

s = Solution1()
org = [1,2,3]
seqs = [[1,2],[1,3]]
assert s.sequenceReconstruction(org, seqs) == False

org = [1,2,3]
seqs = [[1,2]]
assert s.sequenceReconstruction(org, seqs) == False

org = [1,2,3]
seqs = [[1,2],[1,3],[2,3]]
assert s.sequenceReconstruction(org, seqs) == True

org = [4,1,5,2,6,3]
seqs = [[5,2,6,3],[4,1,5,2]]
assert s.sequenceReconstruction(org, seqs) == True

import collections

class Solution2(object):
    '''
    Time:  O(V+E)
    Space: O(E)
    '''
    def sequenceReconstruction(self, org, seqs):
        """
        :type org: List[int]
        :type seqs: List[List[int]]
        :rtype: bool
        """
        graph = collections.defaultdict(set)
        indegree = collections.defaultdict(int)
        integer_set = set()
        for seq in seqs:
            for i in seq:
                integer_set.add(i)
            if len(seq) == 1:
                if seq[0] not in indegree:
                    indegree[seq[0]] = 0
                continue
            for i in range(len(seq)-1):
                if seq[i] not in indegree:
                    indegree[seq[i]] = 0
                if seq[i+1] not in graph[seq[i]]:
                    graph[seq[i]].add(seq[i+1])
                    indegree[seq[i+1]] += 1

        cnt_of_zero_indegree = 0
        res = []
        q = []
        for i in indegree:
            if indegree[i] == 0:
                cnt_of_zero_indegree += 1
                if cnt_of_zero_indegree > 1:
                    return False
                q.append(i)

        while q:
            i = q.pop()
            res.append(i)
            cnt_of_zero_indegree = 0
            for j in graph[i]:
                indegree[j] -= 1
                if indegree[j] == 0:
                    cnt_of_zero_indegree += 1
                    if cnt_of_zero_indegree > 1:
                        return False
                    q.append(j)
        return res == org and len(org) == len(integer_set)

s = Solution2()
org = [1,2,3]
seqs = [[1,2],[1,3]]
assert s.sequenceReconstruction(org, seqs) == False

org = [1,2,3]
seqs = [[1,2]]
assert s.sequenceReconstruction(org, seqs) == False

org = [1,2,3]
seqs = [[1,2],[1,3],[2,3]]
assert s.sequenceReconstruction(org, seqs) == True

org = [4,1,5,2,6,3]
seqs = [[5,2,6,3],[4,1,5,2]]
assert s.sequenceReconstruction(org, seqs) == True

See also:

https://leetcode.com/problems/sequence-reconstruction/